﻿namespace Graph;

public class BFSBipartitionDetection
{
    private IGraph  G;
    private bool[] visited;
    private Queue<int> queue = new Queue<int>();
    private bool[] colors; //红为false，绿为true，初始染色为红

    public bool IsBipartite { get; private set; } = true;

    public BFSBipartitionDetection(IGraph G)
    {
        this.G = G;
        visited = new bool[G.V];
        colors = new bool[G.V];

        for (int v = 0; v < G.V; v++)
        {
            if (!visited[v])
            {
                BFS(v);
            }
        }
    }

    private void BFS(int s)
    {
        visited[s] = true;
        queue.Enqueue(s);

        while (queue.Count != 0)
        {
            int v = queue.Dequeue();

            foreach (int w in G.Adj(v))
            {
                if (!visited[w])
                {
                    visited[w] = true;
                    colors[w] = !colors[v];
                    queue.Enqueue(w);
                }
                else if (colors[w] == colors[v])
                {
                    IsBipartite = false;
                    break;
                }
            }
        }
    }

    //验证
    static void Main(string[] args)
    {
        IGraph graph = new AdjLinkList("图的二分检测/g.txt");
        BFSBipartitionDetection bipartitionDetection = new(graph);
        Console.WriteLine(bipartitionDetection.IsBipartite);

        Console.Read();
    }
}
